package hot_problems_100;
import java.util.*;

class P10_0560 {
    /*
    * 求滑动窗口的最大值
    *
    * */

    /*
    * 单调队列思想：这是一个永远递减的队列，不允许出现递增，如果出现递增，则将之前的较小的元素移除
    *
    * */
    public int[] maxSlidingWindow(int[] nums, int k) {
        int[] res = new int[nums.length-k+1];
        Deque<Integer> deque = new LinkedList<>();
        for(int i=0; i<nums.length; i++){
            if(deque.isEmpty()){
                deque.addLast(i);
            } else {
                if(deque.peekFirst()<i-k+1) deque.removeFirst();
                if(!deque.isEmpty()){
                    if(nums[deque.peekLast()] <= nums[i])
                        while(!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]) deque.removeLast();
                }
                deque.addLast(i);
            }
            if(i>=k-1) res[i-k+1] = nums[deque.peekFirst()];
        }
        return res;
    }

    public static void main(String[] args){
        P10_0560 p = new P10_0560();
        int[] nums = {1,3,1,2,0,5};
        int k = 3;
        int[] res = p.maxSlidingWindow(nums, k);
        for(int i=0; i<res.length; i++){
            System.out.println(res[i]+" ");
        }
    }
}